It is well known in the art that depth related displacements in stereo pairs always occur along lines, the epipolar lines. Traditionally, this constraint has been most widely used to decompose a matching process into a number of independent matching of pairs of lines. However, the solutions obtained on consecutive epipolar lines can vary significantly and create artifacts across epipolar lines that affect in particular object boundaries that are perpendicular to the epipolar lines (i.e. a vertical boundary with horizontal epipolar lines). Consequently, several attempts have been made to relate the solutions of consecutive lines.
In an article by Y. Ohta and T. Kanade, entitled "Stereo by intra and inter-scanline using dynamic programming", IEEE Trans. Pattern Analysis and Machine Intelligence, 7(2):139, 1996, dynamic programming is used to first match epipolar lines and then iteratively improve the solutions obtained by using vertical edges as reference. In an article by I. J. Cox, S. Hingorani, B. M. Maggs and S. B. Rao, entitled "A maximum likelihood stereo algorithm", Computer Vision and Image Understanding, 63(3):542-567, 1996, a probabilistic approach is used to relate the individual matchings obtained by dynamic programming to improve the depth map quality. Finally, in an article by P. N. Belhumeur, entitled "A bayesian approach to binocular stereopsis", Int. J. Computer vision, 19(3):237-260, 1996, a Bayesian approach is described. Unfortunately, the optimality and simplicity of dynamic programming applied to a single pair of epipolar lines cannot be generalized directly to the matching of all epipolar lines at once. For such a case, only iterative or approximate solutions are available. One such iterative or approximate solution is described in Ohta et al, supra.
The dynamic programming approach for finding a matching path between two lines cannot be generalized to matching two full images at once. However, I have discovered that a formulation using maximum-flow estimation can be used instead which allows matching full images without concern for epipolar lines.